package easy.平衡二叉树;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }

    //计算二叉树的最大深度
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = maxDepth(root.left);
            int rightHeight = maxDepth(root.right);
            return 1 + Math.max(leftHeight, rightHeight);
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1, new TreeNode(9),
                new TreeNode(20, new TreeNode(15), new TreeNode(7)));
        TreeNode root2 = new TreeNode(1, new TreeNode(2, new TreeNode(3,
                new TreeNode(4), new TreeNode(4)), new TreeNode(3)),
                new TreeNode(2));
        Solution solution = new Solution();
        System.out.println(solution.isBalanced(root));
        System.out.println(solution.isBalanced(root2));
    }
}
